package com.shindo.structure.class01;

/**
 * 二分法 降低算法复杂度
 * 查找有序数组中是否存在某个数
 */
public class Code04_BSExist {

    public static boolean exist(int[] sortedArr, int num) {
        if (null == sortedArr || sortedArr.length == 0) {
            return false;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        while (L < R) {//L ..R 范围上至少有两个数的时候，才会进行二分
            //下面求mid值的写法有溢出风险，最好换成位运算的写法
            //mid = L + (R - L)/2 可以简化为： L + (R - L) >> 1
            int mid = (L + R) / 2;
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        //最后再验一下，因为上面的二分有可能剩下最后一个数
        return sortedArr[L] == num;
    }

    public static void main(String[] args) {
        int[] testArr = new int[]{1, 3, 5, 8, 11, 12, 18, 23, 25};
        System.out.println(exist(testArr, 2));
    }
}
